KNN算法三要素

KNN算法我們主要考慮三個重要的要素，對於固定的訓練集，只要這三點確定了，算法的預測方式也就決定了。這三個最終的要素距離度量、 k值的選擇和分類決策規則決定。

距離度量

特征空間中兩個實例點的距離是兩個實例點相似程度的反映。k近鄰模型的特征空間一般是n維實數向量空間 ，使用的距離是一般是歐式距離，也可以是其他距離。由不同的距離度量所確定的最近鄰點是不同的。

K值的選擇

k值的大小決定了鄰域的大小。較小的k值使得預測結果對近鄰的點非常敏感，如果近鄰的點恰好是噪聲，則預測便會出錯。話句話說，k值的減小意味著整體模型變得覆雜，容易發生過擬合。較大的k值會讓輸入實例中較遠的（不相似的）訓練實例對預測起作用，使預測發生錯誤，k值的增大意味著整體模型變得簡單。在實際的應用中，一般采用一個比較小的K值。並采用交叉驗證的方法，選取一個最優的K值。一個極端是k等於樣本數m，則完全沒有分類，此時無論輸入實例是什麽，都只是簡單的預測它屬於在訓練實例中最多的類，模型過於簡單。

分類決策規則決定

k近鄰法中的分類規則往往是多數表決，即由輸入實例的k個近鄰的訓練實例中的多數類決定輸入的實例。但這個規則存在一個潛在的問題：有可能多個類別的投票數同為最高。這個時候，可以通過以下幾個途徑解決該問題：

從投票數相同的最高類別中隨機地選擇一個；
通過距離來進一步給票數加權；
減少K的個數，直到找到一個唯一的最高票數標簽。
近鄰算法中的分類決策多采用多數表決的方法進行。它等價於尋求經驗風險最小化。